package tree

import "math"

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn08xg/
// 当前未通过用例: https://leetcode-cn.com/submissions/detail/154008594/
// 是否是二叉搜索树
// 算法: 通过栈遍历 / 递归
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	return recurCheckIsBST(root, math.MinInt16, math.MaxInt16)
}

// 递归检查树是否合法
// root: 当前节点
// min、max 记录当前节点 需要"继承" 前面父节点的关系，至少满足的大小关系
func recurCheckIsBST(root *TreeNode, min int, max int) bool {
	if nil == root {
		return true
	}
	left, right := root.Left, root.Right
	isLeftNodeBST, isRightNodeBST := true, true
	if nil != left && (left.Val >= root.Val || left.Val <= min) {
		isLeftNodeBST = false
	}
	if isLeftNodeBST {
		isLeftNodeBST = recurCheckIsBST(left, min, root.Val)
	}
	if nil != right && (right.Val <= root.Val || right.Val >= max) {
		isRightNodeBST = false
	}
	if isRightNodeBST {
		isRightNodeBST = recurCheckIsBST(right, root.Val, max)
	}
	return isLeftNodeBST && isRightNodeBST
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}
